
#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 100

typedef int ELEMTYPE;

typedef struct Queue
{
	int* arr;
	int front;
	int rear;
}Queue;

void Init(Queue* pq)
{
	pq->arr = (int*)malloc(sizeof(int) * MAXSIZE);
	pq->front = pq->rear = 0;
}

void Push(Queue* pq, int val)
{
	pq->arr[pq->rear] = val;
	pq->rear = (pq->rear + 1) % MAXSIZE;
}

void Pop(Queue* pq)
{
	pq->front = (pq->front + 1) % MAXSIZE;
}

bool Empty(Queue* pq)
{
	return pq->front == pq->rear;
}

int Front(Queue* pq)
{
	return pq->arr[pq->front];
}

int Size(Queue* pq)
{
	return (pq->rear - pq->front + MAXSIZE) % MAXSIZE;
}

void Destroy(Queue* pq)
{
	free(pq->arr);
	pq->arr = NULL;
	pq->front = pq->rear = 0;
}

typedef struct 
{
	Queue q1;
	Queue q2;
} MyStack;


MyStack* myStackCreate() 
{
	MyStack* ps = (MyStack*)malloc(sizeof(MyStack));
	Init(&ps->q1);
	Init(&ps->q2);
	return ps;
}

void myStackPush(MyStack* obj, int x) 
{
	Push(&obj->q1, x);
}

int myStackPop(MyStack* obj) 
{
	int rel = 0;
	if (!Empty(&obj->q1))
	{
		while (Size(&obj->q1) > 1)
		{
			Push(&obj->q2, Front(&obj->q1));
			Pop(&obj->q1);
		}
		rel = Front(&obj->q1);
		Pop(&obj->q1);
	}
	else
	{
		while (Size(&obj->q2) > 1)
		{
			Push(&obj->q1, Front(&obj->q2));
			Pop(&obj->q2);
		}
		rel = Front(&obj->q2);
		Pop(&obj->q2);
	}
	return rel;
}

int myStackTop(MyStack* obj) 
{
	int rel = 0;
	if (!Empty(&obj->q1))
	{
		while (Size(&obj->q1) > 1)
		{
			Push(&obj->q2, Front(&obj->q1));
			Pop(&obj->q1);
		}
		rel = Front(&obj->q1);
		Push(&obj->q2, Front(&obj->q1));
		Pop(&obj->q1);
	}
	else
	{
		while (Size(&obj->q2) > 1)
		{
			Push(&obj->q1, Front(&obj->q2));
			Pop(&obj->q2);
		}
		rel = Front(&obj->q2);
		Push(&obj->q1, Front(&obj->q2));
		Pop(&obj->q2);
	}
	return rel;
}

bool myStackEmpty(MyStack* obj) 
{
	return Empty(&obj->q1) && Empty(&obj->q2);
}

void myStackFree(MyStack* obj) 
{
	Destroy(&obj->q1);
	Destroy(&obj->q2);
	free(obj);
	obj = NULL;
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/

int main()
{
	MyStack* s = myStackCreate();

	myStackPush(s, 1);
	myStackPush(s, 2);

	printf("%d\n", myStackTop(s));

	printf("%d\n", myStackPop(s));
	
	printf("%d\n", myStackPop(s));

	myStackEmpty(s);

	return 0;
}